Count Subarrays with Given XOR

Count Subarrays with Given XOR — GeeksforGeeks

Given an array and an integer k, count the number of contiguous subarrays whose elements XOR to exactly k.

Approach

1. XOR anything with itself cancels itself out.
2. XOR is commutative

So, I need to find subarrays where I can find an X such that, $$X = P \oplus k$$ Set 0's count to 1. A dictionary stores prefixes we've seen and the count it has occurred. At every step, check if I can find an X. Increment counter to count of times I saw X. Then add the current P to the map with the count.

Remarks

This is related to largest subarray with 0 sum.

Related

• Arrays and Hashing
• Largest subarray with 0 sum
• Subarrays equals K
• Single Element